//
// Description: 5253. 找到指定长度的回文数
// Created by Loading on 2022/3/27.
//

#include <bits/stdc++.h>

using namespace std;

vector<long long> kthPalindrome(vector<int> &queries, int intLength) {
    /* 回文数的前一半递增，例如：101，111，121……，前一半为10，11，12…… */
    /* 找到前一半，将前一半反转后叠加到后边即可，注意intLength奇偶性 */
    vector<long long> res;
    int k = (intLength + 1) / 2;
    int p = pow(10, k - 1);
    for (auto x : queries) {
        // 一位和两位的回文数有9个，三位和四位的回文数有90个……
        if (x > 9 * p) {
            res.emplace_back(-1);
        } else {
            // 找到第x个数的前一半
            long long tmp = p + x - 1;
            auto s = to_string(tmp);
            // intLength为奇数则舍弃最后一位后反转，偶数则直接反转
            s.resize(intLength - k);
            reverse(s.begin(), s.end());
            // 将反转后的数叠加至后边
            tmp = tmp * (long long) pow(10, intLength - k) + strtoll(s.c_str(), nullptr, 10);
            res.emplace_back(tmp);
        }
    }

    return res;
}

int main() {
    vector<int> queries{1, 2, 3, 4, 5, 90, 91, 999999999};
    int intLength = 15;
    auto res = kthPalindrome(queries, intLength);
    for (auto x : res) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}